class Solution {
public:
    TreeNode* dfs(TreeNode* root, int o1, int o2) {
        if (!root) return nullptr;
        if (root->val == o1 || root->val == o2) return root;
        TreeNode* t1 = dfs(root->left, o1, o2);
        TreeNode* t2 = dfs(root->right, o1, o2);
        if (!t1) return t2;
        if (!t2) return t1;
        return root;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        return dfs(root, o1, o2)->val;
    }
};

#include <vector>
class Solution {
public:
    bool flag = false;
    void dfs(TreeNode* root, vector<int>& path, int o) {
        if (flag || !root) return;
        path.push_back(root->val);
        if (root->val == o) {
            flag = true;
            return;
        }
        dfs(root->left, path, o);
        dfs(root->right, path, o);
        if (flag) return;
        path.pop_back();
    }   
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        vector<int> p1, p2;
        dfs(root, p1, o1);
        flag = false;
        dfs(root, p2, o2);
        int leng = min(p1.size(), p2.size());
        for (int i = 1; i < leng; i++) {
            if (p1[i] != p2[i]) return p1[i-1];
        }
        return p1[leng-1];
    }
};